﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
using System.Drawing;

namespace CartoLab.ShortestPath
{
    /// <summary>
    /// RoutePlanner 提供图算法中常用的路径规划功能。
    /// 2005.09.06
    /// </summary>
    public class RoutePlanner:ICloneable
    {
        private List<Node> nodesList = new List<Node>();
        private List<Edge> edgesList = new List<Edge>();

        public Edge[] Edges
        {
            get { return edgesList.ToArray(); }
        }
        public RoutePlanner(Node[] nodes, Edge[] edges)
        {
            this.nodesList.AddRange(nodes);
            this.edgesList.AddRange(edges);
            UpdateNodesInEdges();
        }

        private void UpdateNodesInEdges()
        {
            int loop = 0;
            foreach (Edge edge in edgesList)
            {
                foreach (Node node in nodesList)
                {
                    if (edge.StartNodeID == node.ID)
                    {
                        edge.StartNode = node;
                    }
                    if (edge.EndNodeID == node.ID)
                    {
                        edge.EndNode = node;
                    }
                }
                ++loop;
            }
        }

        private List<RoutePlanResult> planResultList = new List<RoutePlanResult>();
        public RoutePlanResult[] PlanResult
        {
            get
            {
                return this.planResultList.ToArray();
            }
        }

        public void AddRouteResult(RoutePlanResult plan)
        {
            //this.planResultList.Clear();
            this.planResultList.Add(plan);
        }

        public void RemoveRouteResult(RoutePlanResult plan)
        {
            this.planResultList.Remove(plan);
        }

        public void ClearRouteResult()
        {
            this.planResultList.Clear();
        }

        //获取权值最小的路径
        public RoutePlanResult Plan(string originID, string destID)
        {
            foreach (Node node in this.nodesList)
            {
                if (node.Edges.Length == 0)
                {
                    int m = 99;
                }
            }

            PlanCourse planCourse = new PlanCourse(nodesList.ToArray(), originID);

            Node curNode = this.GetMinWeightRudeNode(planCourse, originID);

            #region 计算过程
            while (curNode != null)
            {
                PassedPath curPath = planCourse[curNode.ID];
                foreach (Edge edge in curNode.Edges)
                {
                    PassedPath targetPath = planCourse[edge.EndNodeID];
                    double tempWeight = curPath.Weight + edge.Weight;

                    if (tempWeight < targetPath.Weight)
                    {
                        targetPath.Weight = tempWeight;
                        targetPath.ClearPassedIDList();

                        for (int i = 0; i < curPath.PassedIDList.Length; i++)
                        {
                            targetPath.AddPassedNode(curPath.PassedIDList[i]);
                        }

                        targetPath.AddPassedNode(curNode.ID);
                    }
                }

                //标志为已处理
                planCourse[curNode.ID].BeProcessed = true;
                //获取下一个未处理节点
                curNode = this.GetMinWeightRudeNode(planCourse, originID);
            }

            //表示规划结束
            RoutePlanResult result =  this.GetResult(planCourse, destID);
            result.CreateRoute(originID, destID, nodesList.ToArray());
            return result;
        }
        #endregion

        #region GetResult
        //从PlanCourse表中取出目标节点的PassedPath，这个PassedPath即是规划结果
        private RoutePlanResult GetResult(PlanCourse planCourse, string destID)
        {
            PassedPath pPath = planCourse[destID];

            if (pPath.Weight == int.MaxValue)
            {
                RoutePlanResult result1 = new RoutePlanResult(null, int.MaxValue);
                return result1;
            }

            string[] passedNodeIDs = new string[pPath.PassedIDList.Length];
            for (int i = 0; i < passedNodeIDs.Length; i++)
            {
                passedNodeIDs[i] = pPath.PassedIDList[i].ToString();
            }
            RoutePlanResult result = new RoutePlanResult(passedNodeIDs, pPath.Weight);

            return result;
        }
        #endregion

        #region GetMinWeightRudeNode
        //从PlanCourse取出一个当前累积权值最小，并且没有被处理过的节点
        private Node GetMinWeightRudeNode(PlanCourse planCourse, 
                                          string originID)
        {
            double weight = double.MaxValue;
            Node destNode = null;

            foreach (Node node in nodesList)
            {
                if (node.ID == originID)
                {
                    continue;
                }

                PassedPath pPath = planCourse[node.ID];
                if (pPath.BeProcessed)
                {
                    continue;
                }

                if (pPath.Weight < weight)
                {
                    weight = pPath.Weight;
                    destNode = node;
                }
            }

            return destNode;
        }
        #endregion

        public void RenderRoutes(Graphics g)
        {
            foreach (Edge edge in edgesList)
            {
                edge.Render(g);
            }
            foreach (Node node in nodesList)
            {
                node.Render(g);
            }
            foreach (RoutePlanResult plan in this.planResultList)
            {
                plan.Render(g);
            }
        }

        /// <summary>
        /// 删除node，返回与node相关的edge
        /// </summary>
        /// <param name="node"></param>
        /// <returns></returns>
        public Dictionary<Node, Edge> ReomoveNode(Node node)
        {
            this.nodesList.Remove(node);
            foreach (Edge edge in node.Edges)
            {
                this.edgesList.Remove(edge);
            }
            List<Edge> edgesRemoved = new List<Edge>();
            foreach (Edge edge in this.Edges)
            {
                if (edge.StartNodeID == node.ID ||
                    edge.EndNodeID == node.ID)
                {
                    if (!edgesRemoved.Contains(edge))
                    {
                        edgesRemoved.Add(edge);
                    }
                }
            }
            Dictionary<Node, Edge> result = new Dictionary<Node, Edge>();
            foreach (Edge edge in edgesRemoved)
            {
                this.edgesList.Remove(edge);
                foreach (Node nodeTemp in this.nodesList)
                {
                    if(edge.StartNodeID == nodeTemp.ID)
                    {
                        if (!result.ContainsKey(nodeTemp))
                        {
                            result.Add(nodeTemp, edge);
                        }
                        nodeTemp.RemoveEdge(edge);
                    }
                }
            }

            return result;
        }

        public void AddNode(Node node)
        {
            this.nodesList.Add(node);
            this.edgesList.AddRange(node.Edges);
        }

        public void AddEdges(Dictionary<Node, Edge> nodeEdgeRemoved)
        {
            foreach (Node node in nodeEdgeRemoved.Keys)
            {
                Edge edge = nodeEdgeRemoved[node];
                node.AddEdge(edge);
                if (!this.edgesList.Contains(edge))
                {
                    this.edgesList.Add(edge);
                }
            }
        }


        public object Clone()
        {
            List<Node> nodes = new List<Node>();
            foreach (Node node in this.nodesList)
            {
                Node nodeClone = node.Clone() as Node;
                nodes.Add(nodeClone);
            }
            RoutePlanner result = new RoutePlanner(nodes.ToArray(),
                                                   this.Edges);
            return result;
        }

        public void RemoveEdge(Edge edge)
        {
            foreach (Node node in this.nodesList)
            {
                node.RemoveEdge(edge);
            }
        }

        public Edge[] RemoveEdge(string[] ids)
        {
            List<Edge> result = new List<Edge>();
            for (int i = 0; i < ids.Length - 1; ++i)
            {
                string idStart = ids[i];
                string idEnd = ids[i + 1];

                foreach (Edge edge in this.edgesList)
                {
                    if (edge.StartNodeID == idStart && edge.EndNodeID == idEnd)
                    {
                        result.Add(edge);
                    }
                }

                foreach (Edge edge in result)
                {
                    this.edgesList.Remove(edge);
                    foreach (Node node in this.nodesList)
                    {
                        node.RemoveEdge(edge);
                    }
                }
            }

            return result.ToArray();
        }

        public void AddEdges(Edge[] edges)
        {
            this.edgesList.AddRange(edges);
            foreach (Node node in this.nodesList)
            {
                foreach (Edge edge in edges)
                {
                    if (edge.StartNodeID == node.ID)
                    {
                        node.AddEdge(edge);
                    }
                }
            }
        }
    }
}
